Existing computer systems may manage computer memory dynamically allowing more efficient utilization of available physical memory. Since exact memory requirements needed during execution of a program cannot usually be predicted prior to execution, most computer programs require dynamic memory handling. A dynamic memory manager handles computer memory requests for allocating, freeing, reallocating, deallocating, and defragmenting available memory space within a memory storage heap typically with a goal of performing these tasks as efficiently as possible. In this context, the term “storage heap” refers to a pool of memory used for dynamic memory allocations where arbitrary-sized blocks of memory used by a computer program for the temporary storage of data are allocated and freed in an arbitrary order at run time.
When a program needs a memory block for storing data, the program requests the memory block from a storage heap manager. The manager allocates a block of requested size from the heap and returns a handle or pointer to the block that is then typically used by the requesting program to access the block. When data stored in the block is no longer needed, the requesting program notifies the memory manager that the block can be freed. The manager frees the block of memory making it available again for allocation.
Typically a memory allocator should minimize memory fragmentation (inability to reuse memory that is free), allocation/deallocation time, locality of reference (reduction of page and cache misses), and have an adequate memory error detection mechanism. Typical allocator mechanisms for implementing various placement policies are sequential fit, segregated free lists, indexed fit, and bitmapped fit realized usually using linked lists, lookup tables or indexing tree data structures. In many of these methods each memory block contains hidden header fields with some additional control information (e.g., block size, boundary tags/flags (free/in use status), links to the left/right neighbors, etc.). When one of the memory blocks is corrupted, the whole memory data structure is usually corrupted as well, thus preventing further usage, causing an interruption of execution sequence and error exit. In many current dynamic memory manager implementations, control information about free and allocated blocks is distributed over the whole storage heap together with memory blocks and is not protected. Corruption of a single memory block or its control information can have a disastrous effect on the whole storage heap.
A memory manager may also be responsible for coalescing free blocks to reduce excessive fragmentation of memory resulting from multiple allocations/deallocations of memory blocks of different sizes. Coalescing is a process of combining smaller free blocks into larger free blocks for more efficient memory allocation. In many allocators, an immediate coalescing of a freed block with its left and/or right neighbor is implemented. This placement policy reduces external fragmentation improving memory utilization, avoids postponing work, providing more predictable speed, and improving stability. However, this policy requires a quick inexpensive check to determine whether two memory blocks can be coalesced and a capability of coalescing very fast. Many memory allocators that support general coalescing use boundary tags to implement the coalescing of free memory areas. Each block of memory usually has both header and a footer field containing the size of the block and information indicating whether it is in use. This policy can however lead to a corruption of the whole memory data structure (linked list, lookup table, indexed tree, etc.) if some element within is corrupted. In addition, data structures based on a linear sequential search (e.g., linked lists) are typically slow and therefore not used for managing large heaps. Indexed trees, on the other hand, can manage large heaps but in order to be more efficient frequent enforced rebalancing of a tree is required which is typically a complex (from implementation point of view) and expensive procedure. Hence, there is a need for a high performance, efficient memory allocation method that is both easy to implement and maintain.